package com.lucien.Search;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {
        int [] arr = {1,8,10,89,1000,1000,1000,1000,1234};
//        int resindex = binarySearch(arr,0,arr.length-1,8);
//        System.out.println(resindex);
        List list = binarySearch2(arr,0,arr.length-1,1000);
        System.out.println(list.toString());


    }

    /**
     *
     * @param arr      数组
     * @param left     左索引
     * @param right    右索引
     * @param findval  要查找得值
     * @return
     */
    public static int binarySearch(int [] arr,int left,int right,int findval){
        //如果 left > right时，说明递归整个数组，但是没有找到
        if (left > right){
            return -1;
        }
        int mid = (left + right) / 2;
        int midval = arr[mid];
        if (findval > midval){// 向 右 递归
            return binarySearch(arr,mid + 1,right,findval);
        }else if (findval < midval){// 向 左 递归
            return binarySearch(arr,left,mid - 1,findval);
        }else{
            return mid;
        }
    }

    /**
     当一个有序数组中有多个相同的值时，如何将所有的值都查找到并返回下标
        思路分析：
            1、在找到mid索引值，不要马上返回
            2、向mid值索引值的左边扫描，将所有满足1000的元素下标，加入到集合ArrayList
            3、向mid值索引值的右边扫描，将所有满足1000的元素下标，加入到集合ArrayList
            4、将ArrayList返回

     */
    public static List<Integer> binarySearch2(int [] arr,int left,int right,int findval){
        //如果 left > right时，说明递归整个数组，但是没有找到
        if (left > right){
            return new ArrayList<Integer>();
        }
        int mid = (left + right) / 2;
        int midval = arr[mid];
        if (findval > midval){// 向 右 递归
            return binarySearch2(arr,mid + 1,right,findval);
        }else if (findval < midval){// 向 左 递归
            return binarySearch2(arr,left,mid - 1,findval);
        }else{
            List<Integer> list = new ArrayList<>();
//            向mid值索引值的左边扫描，将所有满足1000的元素下标，加入到集合ArrayList
            int temp = mid - 1;
            while (true){
                if (temp < 0 || arr[temp] != findval){
                    break;
                }
                //否则temp 放到list
                list.add(temp);
                temp -= 1;
            }
                list.add(mid);

//            向mid值索引值的右边扫描，将所有满足1000的元素下标，加入到集合ArrayList
            temp = mid + 1;
            while (true){
                if (temp > arr.length - 1 || arr[temp] != findval){
                    break;
                }
                //否则temp 放到list
                list.add(temp);
                temp += 1;
            }
            return list;
        }
    }
}
